Data Structures
A. ARRAY
Simple Array Traversal and Operations
Description: Arrays are collections of elements stored in contiguous memory locations. They allow efficient access to elements using indices.
// C++ Array Implementation
#include <iostream>
using namespace std;
int main() {
// Array declaration and initialization
int arr[5] = {10, 20, 30, 40, 50};
// Array traversal
cout << "Array elements: ";
for(int i = 0; i < 5; i++) {
cout << arr[i] << " ";
}
cout << endl;
// Accessing elements
cout << "First element: " << arr[0] << endl;
cout << "Last element: " << arr[4] << endl;
// Modifying elements
arr[2] = 35;
cout << "Modified array: ";
for(int i = 0; i < 5; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
#include <iostream>
using namespace std;
int main() {
// Array declaration and initialization
int arr[5] = {10, 20, 30, 40, 50};
// Array traversal
cout << "Array elements: ";
for(int i = 0; i < 5; i++) {
cout << arr[i] << " ";
}
cout << endl;
// Accessing elements
cout << "First element: " << arr[0] << endl;
cout << "Last element: " << arr[4] << endl;
// Modifying elements
arr[2] = 35;
cout << "Modified array: ";
for(int i = 0; i < 5; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
Output:
Array elements: 10 20 30 40 50
First element: 10
Last element: 50
Modified array: 10 20 35 40 50
Array elements: 10 20 30 40 50
First element: 10
Last element: 50
Modified array: 10 20 35 40 50
B. STACKS
Infix to Postfix Conversion
Description: Converts infix expressions (operator between operands) to postfix expressions (operator after operands).
// C++ Infix to Postfix Conversion
#include <iostream>
#include <stack>
#include <cctype>
using namespace std;
int precedence(char op) {
if(op == '+' || op == '-') return 1;
if(op == '*' || op == '/') return 2;
return 0;
}
string infixToPostfix(string infix) {
stack<char> st;
string postfix = "";
for(char c : infix) {
if(isalnum(c)) {
postfix += c;
} else if(c == '(') {
st.push(c);
} else if(c == ')') {
while(!st.empty() && st.top() != '(') {
postfix += st.top();
st.pop();
}
st.pop();
} else {
while(!st.empty() && precedence(st.top()) >= precedence(c)) {
postfix += st.top();
st.pop();
}
st.push(c);
}
}
while(!st.empty()) {
postfix += st.top();
st.pop();
}
return postfix;
}
int main() {
string infix = "a+b*(c-d)";
cout << "Infix: " << infix << endl;
cout << "Postfix: " << infixToPostfix(infix) << endl;
return 0;
}
#include <iostream>
#include <stack>
#include <cctype>
using namespace std;
int precedence(char op) {
if(op == '+' || op == '-') return 1;
if(op == '*' || op == '/') return 2;
return 0;
}
string infixToPostfix(string infix) {
stack<char> st;
string postfix = "";
for(char c : infix) {
if(isalnum(c)) {
postfix += c;
} else if(c == '(') {
st.push(c);
} else if(c == ')') {
while(!st.empty() && st.top() != '(') {
postfix += st.top();
st.pop();
}
st.pop();
} else {
while(!st.empty() && precedence(st.top()) >= precedence(c)) {
postfix += st.top();
st.pop();
}
st.push(c);
}
}
while(!st.empty()) {
postfix += st.top();
st.pop();
}
return postfix;
}
int main() {
string infix = "a+b*(c-d)";
cout << "Infix: " << infix << endl;
cout << "Postfix: " << infixToPostfix(infix) << endl;
return 0;
}
Output:
Infix: a+b*(c-d)
Postfix: abcd-*+
Infix: a+b*(c-d)
Postfix: abcd-*+
Prefix Evaluation
Description: Evaluates prefix expressions (Polish notation) using a stack.
// C++ Prefix Evaluation
#include <iostream>
#include <stack>
#include <cctype>
using namespace std;
int evaluatePrefix(string prefix) {
stack<int> st;
// Traverse from right to left
for(int i = prefix.length() - 1; i >= 0; i--) {
char c = prefix[i];
if(isdigit(c)) {
st.push(c - '0');
} else {
int val1 = st.top(); st.pop();
int val2 = st.top(); st.pop();
switch(c) {
case '+': st.push(val1 + val2); break;
case '-': st.push(val1 - val2); break;
case '*': st.push(val1 * val2); break;
case '/': st.push(val1 / val2); break;
}
}
}
return st.top();
}
int main() {
string prefix = "-+*23*549";
cout << "Prefix: " << prefix << endl;
cout << "Result: " << evaluatePrefix(prefix) << endl;
return 0;
}
#include <iostream>
#include <stack>
#include <cctype>
using namespace std;
int evaluatePrefix(string prefix) {
stack<int> st;
// Traverse from right to left
for(int i = prefix.length() - 1; i >= 0; i--) {
char c = prefix[i];
if(isdigit(c)) {
st.push(c - '0');
} else {
int val1 = st.top(); st.pop();
int val2 = st.top(); st.pop();
switch(c) {
case '+': st.push(val1 + val2); break;
case '-': st.push(val1 - val2); break;
case '*': st.push(val1 * val2); break;
case '/': st.push(val1 / val2); break;
}
}
}
return st.top();
}
int main() {
string prefix = "-+*23*549";
cout << "Prefix: " << prefix << endl;
cout << "Result: " << evaluatePrefix(prefix) << endl;
return 0;
}
Output:
Prefix: -+*23*549
Result: 17
Prefix: -+*23*549
Result: 17
Postfix Evaluation
Description: Evaluates postfix expressions using a stack.
// C++ Postfix Evaluation
#include <iostream>
#include <stack>
#include <cctype>
using namespace std;
int evaluatePostfix(string postfix) {
stack<int> st;
for(char c : postfix) {
if(isdigit(c)) {
st.push(c - '0');
} else {
int val2 = st.top(); st.pop();
int val1 = st.top(); st.pop();
switch(c) {
case '+': st.push(val1 + val2); break;
case '-': st.push(val1 - val2); break;
case '*': st.push(val1 * val2); break;
case '/': st.push(val1 / val2); break;
}
}
}
return st.top();
}
int main() {
string postfix = "23*54*+9-";
cout << "Postfix: " << postfix << endl;
cout << "Result: " << evaluatePostfix(postfix) << endl;
return 0;
}
#include <iostream>
#include <stack>
#include <cctype>
using namespace std;
int evaluatePostfix(string postfix) {
stack<int> st;
for(char c : postfix) {
if(isdigit(c)) {
st.push(c - '0');
} else {
int val2 = st.top(); st.pop();
int val1 = st.top(); st.pop();
switch(c) {
case '+': st.push(val1 + val2); break;
case '-': st.push(val1 - val2); break;
case '*': st.push(val1 * val2); break;
case '/': st.push(val1 / val2); break;
}
}
}
return st.top();
}
int main() {
string postfix = "23*54*+9-";
cout << "Postfix: " << postfix << endl;
cout << "Result: " << evaluatePostfix(postfix) << endl;
return 0;
}
Output:
Postfix: 23*54*+9-
Result: 17
Postfix: 23*54*+9-
Result: 17
C. QUEUES
Queue using Array
Description: Implementation of a queue data structure using arrays with FIFO (First-In-First-Out) principle.
// C++ Queue Implementation using Array
#include <iostream>
using namespace std;
class Queue {
private:
int front, rear, size;
int *arr;
public:
Queue(int s) {
front = rear = -1;
size = s;
arr = new int[size];
}
bool isFull() {
return (rear == size - 1);
}
bool isEmpty() {
return (front == -1 || front > rear);
}
void enqueue(int value) {
if(isFull()) {
cout << "Queue Overflow!" << endl;
return;
}
if(front == -1) front = 0;
arr[++rear] = value;
cout << value << " enqueued to queue" << endl;
}
int dequeue() {
if(isEmpty()) {
cout << "Queue Underflow!" << endl;
return -1;
}
int value = arr[front++];
if(front > rear) front = rear = -1;
return value;
}
int peek() {
if(isEmpty()) {
cout << "Queue is empty!" << endl;
return -1;
}
return arr[front];
}
};
int main() {
Queue q(5);
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
cout << q.dequeue() << " dequeued from queue" << endl;
cout << "Front element is " << q.peek() << endl;
return 0;
}
#include <iostream>
using namespace std;
class Queue {
private:
int front, rear, size;
int *arr;
public:
Queue(int s) {
front = rear = -1;
size = s;
arr = new int[size];
}
bool isFull() {
return (rear == size - 1);
}
bool isEmpty() {
return (front == -1 || front > rear);
}
void enqueue(int value) {
if(isFull()) {
cout << "Queue Overflow!" << endl;
return;
}
if(front == -1) front = 0;
arr[++rear] = value;
cout << value << " enqueued to queue" << endl;
}
int dequeue() {
if(isEmpty()) {
cout << "Queue Underflow!" << endl;
return -1;
}
int value = arr[front++];
if(front > rear) front = rear = -1;
return value;
}
int peek() {
if(isEmpty()) {
cout << "Queue is empty!" << endl;
return -1;
}
return arr[front];
}
};
int main() {
Queue q(5);
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
cout << q.dequeue() << " dequeued from queue" << endl;
cout << "Front element is " << q.peek() << endl;
return 0;
}
Output:
10 enqueued to queue
20 enqueued to queue
30 enqueued to queue
10 dequeued from queue
Front element is 20
10 enqueued to queue
20 enqueued to queue
30 enqueued to queue
10 dequeued from queue
Front element is 20
D. TREES
Binary Tree Traversals
Description: Implementation of inorder, preorder, and postorder traversals for binary trees.
// C++ Binary Tree Traversals
#include <iostream>
using namespace std;
struct Node {
int data;
Node *left, *right;
Node(int value) {
data = value;
left = right = NULL;
}
};
void inorder(Node *root) {
if(root == NULL) return;
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
void preorder(Node *root) {
if(root == NULL) return;
cout << root->data << " ";
preorder(root->left);
preorder(root->right);
}
void postorder(Node *root) {
if(root == NULL) return;
postorder(root->left);
postorder(root->right);
cout << root->data << " ";
}
int main() {
// Creating a sample binary tree
// 1
// / \
// 2 3
// / \
// 4 5
Node *root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
cout << "Inorder traversal: ";
inorder(root);
cout << endl;
cout << "Preorder traversal: ";
preorder(root);
cout << endl;
cout << "Postorder traversal: ";
postorder(root);
cout << endl;
return 0;
}
#include <iostream>
using namespace std;
struct Node {
int data;
Node *left, *right;
Node(int value) {
data = value;
left = right = NULL;
}
};
void inorder(Node *root) {
if(root == NULL) return;
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
void preorder(Node *root) {
if(root == NULL) return;
cout << root->data << " ";
preorder(root->left);
preorder(root->right);
}
void postorder(Node *root) {
if(root == NULL) return;
postorder(root->left);
postorder(root->right);
cout << root->data << " ";
}
int main() {
// Creating a sample binary tree
// 1
// / \
// 2 3
// / \
// 4 5
Node *root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
cout << "Inorder traversal: ";
inorder(root);
cout << endl;
cout << "Preorder traversal: ";
preorder(root);
cout << endl;
cout << "Postorder traversal: ";
postorder(root);
cout << endl;
return 0;
}
Output:
Inorder traversal: 4 2 5 1 3
Preorder traversal: 1 2 4 5 3
Postorder traversal: 4 5 2 3 1
Inorder traversal: 4 2 5 1 3
Preorder traversal: 1 2 4 5 3
Postorder traversal: 4 5 2 3 1